\begin{exercise}
\label{ex:stream_ciphers:identify_OFB}
Identify each of the {\it key stream}, {\it output}, and {\it next
state} functions for the synchronous stream cipher determined by a
block cipher in OFB mode of operation.
\end{exercise}

\begin{exercise}
\label{ex:stream_ciphers:identify_CBC_CFB}
Identify the the {\it key stream} and {\it output} functions for the
asynchronizing stream cipher determined by a block cipher in each of
CBC and 1-bit CFB modes.
\end{exercise}

Linear feedback shift registers (LFSR's) are an efficient way of
describing and generating certain sequences in hardware implementations.
We derive and work with equivalent mathematical descriptions of the
sequences produced by a LFSR, along with some generalized sequences
which do not arise in this way.

A linear feedback shift register is composed of a shift register $R$
which contains a sequence of bits and a feedback function $f$ which
is the bit sum ({\tt xor}) of a subset of the entries of the shift
register.  The shift register contains $n$ memory cells, or stages,
labelled $R_{n-1}$,\dots, $R_1$, $R_0$, each holding one bit.
Each time a bit is needed the entry in stage $R_0$ is output while
the entry in cell $R_i$ is passed to cell $R_{i-1}$ and the top stage
$R_{n-1}$ is updated with the value $f(R)$.

\begin{exercise}
\label{ex:stream_ciphers:LFSR}
Consider the following schematic of a linear feedback shift register:
$$
\xymatrix@R=0.6cm@C=0.4cm{
*+={} \ar@{-}[d] & & \oplus \ar@{-}[ll]
                 & & & & & & *+={} \ar@{->}[llllll] \\
*+={} \ar@{->}[r]  &
*+[F]{\hbox{$R_3$}} \ar@{-}[r]  &
                        *+={}\ar@{->}[r] \ar@{->}[u] &
*+[F]{\hbox{$R_2$}} \ar@{->}[rr] & &
*+[F]{\hbox{$R_1$}} \ar@{->}[rr] & &
*+[F]{\hbox{$R_0$}} \ar@{-}[r] &
                        *+={} \ar@{-}[u] \ar@{->}[r] & \\
}
$$
Let the initial entries of stages $R_i$ be $s_i$, for $0 \le i \le n$.
For each of the following initial entries below:
$$
\begin{array}{ccccc}
& s_3 & s_2 & s_1 & s_0 \\
\hline
{\rm a)} & 0 & 1 & 1 & 0 \\
{\rm b)} & 1 & 1 & 1 & 0 \\
{\rm c)} & 1 & 0 & 1 & 0 \\
{\rm d)} & 1 & 1 & 0 & 0 \\
\end{array}
$$
compute the first 16 bits in the output sequence.  Show that the
output sequence is defined by the initial entries and the recursion
$s_{i+4} = s_{i+3} + s_i$.
\end{exercise}

\begin{exercise}
\label{ex:stream_ciphers:show_definition_LFSR}
Show that every linear feedback register defines and is defined
by a recursion of the form $s_{i+n} = \sum_{j=0}^{n-1} c_j s_{i+j}$,
where the $c_j$ are bits in $\Z/2\Z$; the products $c_j s_{i+j}$ and
the summation are operations in $\Z/2\Z$.

N.B. The ring $\Z/2\Z$ is also referred to as $\F_2$, the unique
finite field of two elements.  Note that the addition operation is
the same {\tt xor} that we have been using and the multiplication
operation is the logical {\tt and} operation.)
\end{exercise}

\begin{exercise}
\label{ex:stream_ciphers:LFSR_power_series}
For a linear feedback register of length $n$, define a power series
$$
s(x) = \sum_{i=1}^\infty s_i x^i
$$
from the output sequence $s_i$.  Suppose that the linear feedback
register defines the recursion $s_{i+n} = \sum_{j=0}^{n-1} c_{n-j} s_{i+j}$.
Define a polynomial $g(x) = 1 + \sum_{j=1}^{n-1} c_j x^j$.
Show that $f(x) = g(x) s(x)$ is a polynomial, that is, all of its
coefficients are eventually zero.  What is the polynomial $f(x)$?
\end{exercise}

\begin{exercise}
\label{ex:stream_ciphers:LFSR_construct_power_series}
In the previous exercise we showed that the power series $s(x)$
has the form $f(x)/g(x)$ in the power series ring $\F_2[[x]]$.
In Sage it is possible to form power series rings in the following
way
{\rm
\begin{lstlisting}
sage: F2 = FiniteField(2)
sage: PS.<x> = PowerSeriesRing(F2)
sage: f = x^2 + x
sage: g = x^3 + x + 1
sage: f/g + O(x^16)
x + x^4 + x^5 + x^6 + x^8 + x^11 + x^12 + x^13 + x^15 + O(x^16)
\end{lstlisting}
}

Consider the linear feedback shift register at the beginning of
the worksheet.  Construct the corresponding power series and verify
that these are the same of the output sequences that you computed.
\end{exercise}

\noindent{\bf Statistical Properties.}
The output of a linear feedback shift operator of length $n$ has a
period, which must divide $2^n-1$.  The period is independent of the
initial state, provided it is non-zero.  If the period equals $2^n-1$,
the output sequence is said to be an $m$-sequence.  The following
theorem describes the statistical properties of $m$-sequences.

\begin{theorem}
Let $s = s_0 s_1 \dots$ be an $m$-sequence, and let $k$ be an integer
with $1 \le k \le n$.  Then in each subsequence of $s$ of length
$2^n + k - 2$, every finite nonzero binary sequence of length $k$
appears as a subsequence exactly $2^{n-k}$ times, and the length $k$
zero subsequence appears exactly $2^{n-k}-1$ times.
\end{theorem}

A polynomial $g(x)$ in $\F_2[x]$ is {\em irreducible} if it is not
the product of two polynomials of degree greater than zero.
An irreducible polynomial $g(x)$ of degree $n$ is {\em primitive}
if $g(x)$ divides $x^N-1$ for $N = 2^n-1$ and no smaller value of $N$.
(Equivalently, $g(x)$ is primitive if the powers $x^i$ are distinct
modulo $g(x)$, for $i$ with $1 \le i \le 2^n-1$.)

\noindent{\bf Linear Complexity.}
A linear feedback shift register is said to generate a binary
sequence $s$ if there exists some initial state for which its output
sequence is $s$.  The linear complexity $L(s)$ of an infinite sequence
$s$ is defined to be zero if $s$ is the zero sequence, infinity if $s$
is generated by no linear feedback shift register, and otherwise equal
to the minimal length of a linear feedback shift register generating
$s$.  The linear complexity $L(s)$ of a finite sequence $s$ is defined
to be the minimal length of a linear feedback shift register with initial
sequence $s$ for some initial state.

\noindent{\bf Linear Complexity Profile.}
For a sequence $s$, define $L_j(s)$ to be the linear complexity of the
first $j$ terms of the sequence.  The linear complexity profile of
an infinite sequence $s$ is defined to be the infinite sequence $L_1(s),
L_2(s),\dots$, and for a finite sequence $s = s_0 s_1 \dots s_{N-1}$ is
defined to be the finite sequence $L_1(s),L_2(s),\dots,L_n(s)$.


\noindent{\bf LFSR Cryptosystems}
We introduce new utilities for binary stream cryptosystems based on
linear feedback shift registers.  The functions \verb!binary_encoding! and
\verb!binary_decoding! convert ASCII text into its bit sequence and back.
In addition, the new binary cryptosystems are:
\begin{center}
{\tt LFSRCryptosystem} \\
{\tt ShrinkingGeneratorCryptosystem}
\end{center}
Unlike the encoding function \verb!strip_encoding! we have used so far, the
function \verb!binary_encoding! is information-preserving, taking 8-bit ASCII
input and returning the binary encoding string.  The inverse function
\verb!binary_decoding! recovers the original text.

A linear feedback shift register cryptosystem is created in Sage
using the function {\tt LFSRCryptosystem}, taking no arguments.
A key is defined by means of a pair, consisting of the connection
polynomial $g(x)$ over $\F_2$ and a initial bit sequence of length equal
to the degree of the sequence.  A sample use of the cryptosystem follows.
The shrinking generator cryptosystem is a cryptosystem based on a pair
of LFSR's as defined in class.
{\rm
\begin{lstlisting}
sage: F2 = FiniteField(2)
sage: P2.<x> = PolynomialRing(F2)
sage: g = x^17 + x^5 + 1
sage: IS = [ F2.random_element() for i in range(17) ]
sage: LFSR = LFSRCryptosystem()
sage: PT = LFSR.encoding("The dog ate my assignment."); PT
010101000110100001100101001000000110010001101111011001110
010000001100001011101000110010100100000011011010111100100
100000011000010111001101110011011010010110011101101110011
0110101100101011011100111010000101110
sage: K = (g,IS)
sage: e = LFSR(K)
sage: CT = e(PT)
sage: PT == e(CT)
True
\end{lstlisting}
}
Note that the encoding of the message is not ciphertext -- this is the
standard ASCII bit encoding.

\begin{exercise}
\label{ex:stream_ciphers:coefficient_sequence_draw_LFSR}
Consider the coefficient sequence for $f(x)/g(x)$ in $\F_2[[x]]$,
where $g(x) = 1 + x + x^4$ and $f(x) = 1 + x^3$.  Is $g(x)$ an
irreducible polynomial?  A primitive polynomial?  Draw the associated
linear feedback shift register.  What is the initial state of the
shift register?
\end{exercise}

\begin{exercise}
\label{ex:stream_ciphers:compute_linear_complexity}
Compute the linear complexity of the sequences $11$, $1011$, $10101$,
$10110$, and $10011$.
\end{exercise}

\begin{exercise}
\label{ex:stream_ciphers:compute_first_8_terms_linear_complexity}
Compute the first $8$ terms of the linear complexity profile of
the coefficient sequence from Exercise 1.
\end{exercise}

\begin{exercise}
\label{ex:stream_ciphers:practice_encode_decode_LFSR}
Practice encoding and enciphering with the LFSR stream cryptosystem.
The function \verb!binary_decoding! easily converts this back to ASCII text.
Use these functions to verify that {\tt PT} is just the binary encoding
of the original plaintext message and that the ciphertext is enciphered.
\end{exercise}

\begin{exercise}
\label{ex:stream_ciphers:inverse_equal_itself}
Since the LFSR is the bitsum of the binary keystream, generated by the
connection polynomial and initial state, why must the inverse key be equal
to the key itself?
\end{exercise}
